Ansage vorweg. Ich wurde angesprochen von Leuten, die hinsichtlich des Scheins Probleme mit den

Gruppen aber nicht den Individualpunkten haben. Diesbezüglich hatte ich noch eine

Detailregelung vergessen anzusagen. Man kann, wenn man da Probleme hat, Individualpunkte zum

Kurs eins zu eins in Gruppenpunkte umtauschen. Dann stehen sie allerdings nicht mehr für die

Bonusregelung zur Verfügung. Also die, die man umgetauscht hat nicht, die restlichen natürlich

schon. Wohlgemerkt, diese Regelung ist nicht optional. Also es gibt jetzt nicht die Möglichkeit,

Bonuspunkte mitzunehmen durch den Schein zu fallen und den Schein nächstes Semester nochmal

zu probieren. Das machen wir nicht mit. Ja, das soweit angekommen. Ich nehme an, wie die jetzt

im Saal sind, interessiert das ohnehin nicht. Gut. Okay, ja heute wird besonders lustig. Ich

habe nämlich meine Notizen zu Hause liegen lassen. So, also Reduktionen sind ein besonders wichtiges

Thema in der Komplexitätstheorie selbstverständlich, weil sie eben dazu dienen, die exakte Komplexität

von Problemen zu bestimmen. Sie kommen vor auf den laufenden Aufgaben zetteln und es wird ganz

sicher auch mindestens eine Reduktion in der Klausur drankommen. Deswegen machen wir heute

mal sorgfältig zwei Beispiele, in denen wir illustrieren, wie das denn so geht. Mit etwas

Pech kennen Sie das eine dieser Beispiele schon. Das ist NP Härte von Klieg. Ist das bekannt? War

das ein BFS? Klickenproblem, NP-Hard? Ich mache es schlicht und einfach trotzdem nochmal,

ja, also damit wir da wieder reinkommen und als zweites zeigen wir NL Härte des Schleifproblems.

Also, wir machen im Rahmen unseres allgemeinen Nonsens noch mal ein Lämmer vorweg, was noch

mal einfängt, was wir hier tun. Wenn ich eine Klasse C habe

und ein Problem, das F-Hard ist für diese Klasse, also ein Problem C, das F-Hard ist

für Skript C und ich habe ein Problem D, das ist noch schwerer unter diesen F-Reduktionen,

dann ist auch dieses Problem D F-Hard für C erst recht, denn es ist ja noch schwerer

als C. Noch mal kurz gucken, woran das eigentlich hängt. Klar ist das Argument trivial, wir

wollen nur sehen, was da tatsächlich vorkommt in dem Argument. Ja, wie immer müssen wir

der Struktur der Definition folgen, in diesem Falle der Struktur der Definition von F-Hard,

das heißt wir müssen uns vorgeben, ein Problem in dieser Klasse Skript C und zeigen, dass

D schwerer ist als dieses Problem. Das heißt, jetzt gehen wir den Namen aus, wir nennen

das E-Hard und zeigen, E ist F-Reduzierbar auf D. Nun wissen wir, E ist F-Reduzierbar

auf C, weil C F-Hard ist und nach Voraussetzung ist C F-Reduzierbar auf D und wir hatten festgehalten,

dass E F-Reduzierbar auf D ist, weil C F-Hard auf D ist und das ist die Klasse von Reduktionsfunktionen,

diese Skript F abgeschlossen ist unter Komposition. Gut.

So, jetzt also unser erstes Beispiel zum Thema NP-Härte. Es lohnt sich insofern, das nochmal

zu machen, weil vermutlich genauer gesagt das, was in BFS gezeigt worden ist, gewesen sein

wird, dass SAT zum Beispiel P-Time-Hard ist für NP, nehme ich an, also Polyzeitreduktion.

Wir gucken uns die Reduktion nochmal an, also jetzt nicht die auf SAT, wir wollen jetzt

nicht NP-Vollständigkeit von SAT nochmal zeigen. Es sei an dieser Stelle aber gesagt,

dass SAT sogar Logspace vollständig ist, das haben wir auch mehrfach schon erwähnt für

P-Time, Quatsch für NP-Time, also für NP. Und insofern lohnt es sich, SAT in Logspace

auf andere Probleme zu reduzieren, weil die dann nämlich ebenfalls Logspace-Hard für

NP sind. So, und jetzt machen wir also in der Tat eine Logspace-Reduktion von SAT auf ein

anderes Problem, und zwar auf CLICK. Also, Erinnerung an die beiden Probleme. So, wir

nehmen hier einen ungerichteten Graphen, G, mit Menge V von Knoten und Menge E von Kanten.

Was heißt das, dass der ungerichtet ist? Nun, das heißt, dass eine Kante von S nach

T existiert, genau dann, wenn eine Kante von T nach S existiert. Das hat den Effekt, dass

die Kanten im Endeffekt keine Richtung haben, es gibt sie immer in beiden Richtungen, wenn

es sie gibt. So, und jetzt gucken wir uns an, eine Teilmenge der Knoten, und definieren,

dass es heißt, für diese Teilmenge eine Clique zu sein, bzw. eine K-Clique. So ein Ding ist

eine K-Clique für eine Zahl, also eine ganze Zahl, kleinen K, genau dann, wenn erstens

die Menge eben genau kleinen K-Knoten enthält, also sprich, das kleinen K, das gibt also

schlicht und einfach die Größe der Clique an, und für alle Knoten S und T in K gilt,